`
https://leetcode.cn/problems/search-in-rotated-sorted-array/
`

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  const n = nums.length
  let left = -1, right = n - 1
  const last = nums[n - 1]

  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    const val = nums[mid]
    if (target > last && val <= last) {
      // target 在第一段，val 在第二段
      right = mid
    } else if (target <= last && val > last) {
      // val 在第一段，target 在第二段
      left = mid
    }
    // 否则，x 和 target 在同一段，正常二分即可
    else if (val >= target) {
      right = mid
    } else {
      left = mid
    }
  }

  return nums[right] === target ? right : -1
};